Catalogs are used to store metadata about user data (e.g., in a database) or other state or system information. To test catalog access statements, some systems have a run-time deadlock detector. For example, at run-time, it is determined if a catalog access statement which is about to be run has the potential to deadlock with an already-running or another soon to be run catalog access statement. If so, the later catalog access statement is aborted. New techniques which are capable of determining ahead of time (i.e., prior to run time) if two catalog access statements have the potential to deadlock would be desirable.